import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int[][] dp=new int[obstacleGrid.length+1][obstacleGrid[0].length+1];
        dp[0][1]=1;
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(obstacleGrid[i-1][j-1]==1){
                    continue;
                }
                else dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[obstacleGrid.length][obstacleGrid[0].length];
    }
    public int massage(int[] nums) {
        if(nums.length==0) return 0;
        int[] f=new int[nums.length];
        int[] g=new int[nums.length];
        f[0]=nums[0];
        for(int i=1;i<nums.length;i++){
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[nums.length-1],g[nums.length-1]);
    }
    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length,n=dungeon[0].length;
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=n;i++){
            dp[m][i]=Integer.MAX_VALUE;
        }
        for(int i=0;i<=m;i++){
            dp[i][n]=Integer.MAX_VALUE;
        }
        dp[m-1][n]=1;
        dp[m][n-1]=1;
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                dp[i][j]=Math.max(1,dp[i][j]);
            }
        }
        return dp[0][0];
    }
    public int deleteAndEarn(int[] nums) {
        int n=nums.length,maxVal=0;
        for(int val:nums){
            maxVal=Math.max(val,maxVal);
        }
        int[] dp=new int[maxVal+1];
        for(int val:nums){
            dp[val]+=val;
        }
        return rob(dp);
    }
    public int rob(int[] nums){
        int n=nums.length;
        int[] f=new int[n];
        int[] g=new int[n];
        f[0]=nums[0];
        g[0]=0;
        for(int i=1;i<n;i++){
            f[i]=g[i-1]+nums[i];
            g[i]=Math.max(f[i-1],g[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }
    public int minCost(int[][] costs) {
        int m=costs.length,n=costs[0].length;
        int[][] dp=new int[m][3];
        for(int i=0;i<3;i++){
            dp[0][i]=costs[0][i];
        }
        for(int i=1;i<m;i++){
            for(int j=0;j<3;j++){
                dp[i][j]=Math.min(dp[i-1][(j+1)%3],dp[i-1][(j+2)%3])+costs[i][j];
            }
        }
        return Math.min(dp[m-1][0],Math.min(dp[m-1][1],dp[m-1][2]));
    }
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][3];
        dp[0][0]=-prices[0];
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][2]-prices[i]);
            dp[i][1]=dp[i-1][0]+prices[i];
            dp[i][2]=Math.max(dp[i-1][2],dp[i-1][1]);
        }
        return Math.max(dp[n-1][1],dp[n-1][2]);
    }
    public int maxProfit(int[] prices, int fee) {
        int n=prices.length;
        int[] f=new int[n];
        int[] g=new int[n];
        f[0]=-prices[0];
        for(int i=1;i<n;i++){
            f[i]=Math.max(f[i-1],g[i-1]-prices[i]);
            g[i]=Math.max(f[i-1]+prices[i]-fee,g[i-1]);
        }
        return g[n-1];
    }
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
        for(int i=0;i<nums.length;i++){
            if(hashMap.containsKey(nums[i])&&Math.abs(i-hashMap.get(nums[i]))<=k){
                return true;
            }
            hashMap.put(nums[i],i);
        }
        return false;
    }
    public int maxProfit2(int[] prices) {
        int INF=0x3f3f3f;
        int n=prices.length;
        int[][] f=new int[n][3];
        int[][] g=new int[n][3];
        for(int j=0;j<3;j++){//初始化值
            f[0][j]=g[0][j]=-INF;
        }
        f[0][0]=-prices[0];
        g[0][0]=0;
        for(int i=1;i<n;i++){//从左往右从上到下填表
            for(int j=0;j<3;j++){
                f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=g[i-1][j];
                if(j-1>=0) g[i][j]=Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
            }
        }
        return Math.max(g[n-1][0],Math.max(g[n-1][1],g[n-1][2]));
    }
    public int maxProfit(int k,int[] prices) {
        int INF=0x3f3f3f;
        int n=prices.length;
        int[][] f=new int[n][k+1];
        int[][] g=new int[n][k+1];
        for(int j=0;j<=k;j++){
            f[0][j]=g[0][j]=-INF;//初始化值
        }
        f[0][0]=-prices[0];
        g[0][0]=0;
        for(int i=1;i<n;i++){//从左往右从上到下填表
            for(int j=0;j<=k;j++){
                f[i][j]=Math.max(f[i-1][j],g[i-1][j]-prices[i]);
                g[i][j]=g[i-1][j];
                if(j-1>=0) g[i][j]=Math.max(g[i-1][j],f[i-1][j-1]+prices[i]);
            }
        }
        int max=-INF;
        for(int i=0;i<=k;i++){
            max=Math.max(max,g[n-1][i]);
        }
        return max;
    }
}